public class Solution779 {
    public int kthGrammar(int n, int k) {
        k--;
        int cur=0;
        while (n>1){
            if ((k&(1<<(n-2)))!=0) {
                cur = (cur == 0) ? 1 : 0;
            }
            n--;
        }
        return cur;
    }

    public static void main(String[] args) {
        System.out.println(new Solution779().kthGrammar(2,2));
    }
}
